package com.lw.leetcode.sort.c;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 407. 接雨水 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/26 10:37
 */
public class TrapRainWater {

    public static void main(String[] args) {
        TrapRainWater test = new TrapRainWater();

        // 4
//        int[][] arr = {{1,4,3,1,3,2},{3,2,1,3,2,4},{2,3,3,2,3,1}};

        // 10
        int[][] arr = {{3,3,3,3,3},{3,2,2,2,3},{3,2,1,2,3},{3,2,2,2,3},{3,3,3,3,3}};

        int i = test.trapRainWater(arr);
        System.out.println(i);

    }

    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        Set<Integer> set = new HashSet<>();
        int[] as = heightMap[0];
        int[] bs = heightMap[m - 1];
        int t = (m - 1) << 8;
        for (int i = 0; i < n; i++) {
            int a = as[i];
            queue.add((a << 16) + i);
            set.add(i);
            a = bs[i];
            queue.add((a << 16) + t + i);
            set.add(t + i);
        }
        for (int i = 1; i < m - 1; i++) {
            int a = heightMap[i][0];
            queue.add((a << 16) + (i << 8));
            set.add((i << 8));
            a = heightMap[i][n - 1];
            queue.add((a << 16) + (i << 8) + n - 1);
            set.add((i << 8) + n - 1);
        }
        int min = 0;
        int sum = 0;
        int[][] arr = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int poll = queue.poll();
            int v = poll >> 16;
            int x = (poll >> 8) & 0XFF;
            int y = poll & 0XFF;
            if (v < min) {
                sum += (min - v);
            } else {
                min = v;
            }
            for (int[] ints : arr) {
                int a = x + ints[0];
                int b = y + ints[1];
                if (a < 0 || a == m || b < 0 || b == n ) {
                    continue;
                }
                if (set.contains((a << 8) + b)) {
                    continue;
                }
                set.add((a << 8) + b);
                queue.add((heightMap[a][b] << 16) +(a << 8) + b );
            }
        }
        return sum;
    }

}
